Skip to content

Leetcode 115. Distinct Subsequences 题解

题目链接

Leetcode 115. Distinct Subsequences

题目内容

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

解题思路

面对这样的动态规划题目，我们首先需要分析出一个合适的状态转移方程，我们把dp[i][j]规定为第一个字符串从0开始长度为i的字符串和第二个字符串从0开始的长度为j的字符子串匹配的个数

初始情况为 dp[0][0] = 1 dp[0][1-s2.length()] = 1 dp[1-s1.length()][0] = 0

状态转移方程 dp[i][j] = dp[i][j-1] + (s1[i-1] == s2[j-1] ? dp[i-1[j-1] : 0)

分析如下，首先，我们至少会有dp[i][j] = dp[i][j-1] 因为若是s2长度增加，其原来匹配的字符串还会匹配，不会改变

其次，若是s1[i-1] == s2[j-1]原来dp[i-1][j-1]的匹配的个数就可以累计到我们的dp[i][j]中，因为我们可以把原先正确匹配的子字符串的最后一个字符替换成我们新找到的匹配的字符。 到这里我们的状态转移就分析完成了。

Detail结果如下 detai

题目代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.size(),m=t.size();

        int dp[n+1][m+1];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=n;i++)
            dp[i][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(s[i-1]==t[j-1])
                    dp[i][j]+=(dp[i-1][j-1]);
            }
        }
        return dp[n][m];
    }
};